/**
 *  @file IsCircle.c
 *  @desc 实现链表环检测：判断一个单链表是否存在环结构（Floyd判圈算法）
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-25 16:38
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct node {
    int data;
    struct node *next;
} node, *link;

/**
 * 创建一个新节点，赋值并初始化 next 指针
 */
link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

/**
 * 初始化链表头结点，头结点数据一般不参与实际存储
 */
void initNode(link *head) {
    link newNode = createNode(0);  // 头节点值为 0（可不使用）
    if (newNode == NULL) return;
    *head = newNode;
}

/**
 * 打印链表中的所有节点值（遇 NULL 停止）
 * 注意：若链表中有环将陷入死循环
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * 头插法：将新节点插入到 head 之后
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    head->next = newNode;
}

/**
 * 尾插法：插入到链表最后（遍历到最后一个节点）
 */
void istTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

/**
 * 判断链表是否存在环
 * 快慢指针法（Floyd 判圈算法）
 * - slow 每次走一步
 * - fast 每次走两步
 * - 如果链表存在环，fast 一定会追上 slow
 * - 否则，fast 会先到达 NULL
 */
int isCircle(link head) {
    if (head == NULL || head->next == NULL) return 0;

    link slow = head;
    link fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;          // 慢指针走一步
        fast = fast->next->next;    // 快指针走两步

        if (slow == fast) {         // 快慢指针相遇 => 存在环
            return 1;
        }
    }

    return 0;  // fast 到达 NULL => 无环
}

int main() {
    link head = NULL;
    initNode(&head);

    // 构造链表：3 -> 2 -> 1
    istHead(head, 1);
    istHead(head, 2);
    istHead(head, 3);

    printList(head);  // 打印正常链表

    // 环检测：初始无环
    if (isCircle(head)) {
        printf("link have cycle \n");
    } else {
        printf("link haven't cycle \n");
    }

    // 人为制造一个环：将最后一个节点指向第一个数据节点（值为 3）
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = head->next;  // 创建环：尾节点 -> 第一个数据节点（3）

    // 环检测：此时有环
    if (isCircle(head)) {
        printf("link have cycle \n");
    } else {
        printf("link haven't cycle \n");
    }

    return 0;
}
